package com.example.demo.leetcode.classics150;

/**
 * ******************************************************
 *
 * @author liugh9
 * @version 1.0
 * @classname _145最长回文子串
 * @description
 * @date 2023/08/28 10:30
 * <p>
 * ******************************************************
 */
public class _145最长回文子串 {
    public String longestPalindrome(String s) {
        int length = s.length();
        if (s.length() < 2) {
            return s;
        }
        // 表示：子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，即可以取到 s[i] 和 s[j]
        boolean[][] dp = new boolean[length][length];

        for (int i = 0; i < length; i++) {
            dp[i][i] = true;
        }
        int begin = 0;
        int maxLen = 1;
        for (int i = 1; i < s.length(); i++) {
            for (int j = 0; j <= i; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    if (i - j < 3) {
                        dp[j][i] = true;
                    } else {
                        dp[j][i] = dp[j + 1][i - 1];
                    }
                } else {
                    dp[j][i] = false;
                }

                if (dp[j][i]) {
                    int len = i - j + 1;
                    if (len >= maxLen) {
                        begin = j;
                        maxLen = len;
                    }
                }
            }
        }
        return s.substring(begin, begin + maxLen);
    }
}
